1. Field
This disclosure relates generally to semiconductor processors, and more specifically, to semiconductor processors having branch target buffers.
2. Related Art
Branch prediction is a common technique used to avoid or reduce times when the processor is idle. Often included in branch prediction is use of a branch target buffer (BTB) that is used to store branch information that is expected to re-used in order to accelerate the execution of branch instructions. BTB entries are used to speed up the process of fetching a branch target instruction located at the branch destination by caching information associated with a branch instruction within a BTB entry. When executing the branch instruction, the destination of the branch instruction (the branch target instruction) is loaded into an instruction queue within the processor. Preferably an entry for the predicted branch is in the BTB so that the branch target can be quickly obtained and loaded into the instruction queue. It takes longer to obtain and load a branch target that is not in the BTB with the result that there may be clock cycles where the central processing unit (CPU) is idle. Thus, it is desirable for the BTB to be loaded such that every time there is a branch there is a hit in the BTB. This is not likely to be accomplished but it is desirable to have few times where the branch target must be obtained outside the BTB. An overview of branch prediction issues and alternatives for BTB design are presented in J. K. L. Lee and A. J. Smith. “Branch prediction strategies and branch target buffer Design”. Computer, 17(1), January 1984.
Supplemental branch predictor structures may be combined with a BTB in order to enhance branch performance as well. Since BTB entries contain branch target information along with an optional predictor, they are large, and only a limited number of entries may be provided. In order to supplement branch performance, one or more additional branch predictor structures may be used in conjunction with a BTB to predict the direction of unresolved conditional branches, and allow for speculative fetching and optional execution of a predicted branch path. One such structure commonly used is a branch history table (BHT) which contains a collection of small predictors. No branch target information is stored, thus the capacity of a BHT may be larger for a given area than a BTB. In a BHT, a history of previous branch outcomes is stored for each branch, or for a global history of branch outcomes, and the table is searched to obtain a branch prediction. BHT predictors may be built with high degrees of accuracy with moderate costs. Note that with a BHT, the execution time is larger than if the branch hits in the BTB, but is reduced relative to not using a branch predictor. A good survey of BHT styles, and more complex structures may be found in S. McFarling, “Combining Branch Predictors”, DEC WRL-TN-36.
In addition to the BTB and BHT structures described, another branch acceleration technique is use of a confidence predictor. Confidence predictors assign a confidence level for assessing the likelihood that a branch prediction is correct. A branch predictor confidence mechanism may be used to modify a prediction obtained from a branch predictor based on the confidence level provided, in order to further increase the effectiveness of branch prediction. Confidence predictors may also be used in hybrid branch prediction schemes as a dynamic selector. In a hybrid branch prediction scheme, multiple predictors are implemented, and a selection is made from one of the predictors for each branch. This selection may be based on a confidence predictor, or on confidence logic which attempts to ascertain the best predictor for each branch outcome. Additional information on confidence predictors and on confidence logic may be found in E. Jacobsen, E. Rotenberg, and J. E. Smith, “Assigning Confidence to Conditional Branch Predictions”, MICRO-29.
One technique for increasing the likelihood that the branch is in the BTB is for the BTB to have a large storage capacity. Increasing the size of the BTB increases the cost of the BTB, thus increasing the area of the integrated circuit that has the processor. Although, the area increase may be small, it can be significant, especially for low cost processors. Thus, there is a need for a technique, that does not require additional storage in the BTB, for avoiding or reducing the situations where the loading of the buffer with branch targets results in clock cycles where the processor is idle.